package simple;


import data.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/4/25 22:08
 */
public class No501_二叉搜索树中的众数 {
    public static void main(String[] args) {
        Solution501 solution501 = new Solution501();
        TreeNode treeNode = new TreeNode(1);
        treeNode.right = new TreeNode(2);
        treeNode.right.left = new TreeNode(2);

        int[] mode = solution501.findMode(treeNode);
        System.out.println(mode);
    }
}

class Solution501 {
    //定义全局变量
    int base = -934579;
    int count = -34543;
    int max = 1;
    public int[] findMode(TreeNode root) {
        // 一次遍历
        // 非递减
        List<Integer> list = new ArrayList<>();
        findMode(root, list);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public void findMode(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        //中序遍历
        findMode(root.left, list);
        //处理这里
        if (base != root.val) {
            count = 1;
            base = root.val;
        } else {
            count++;
        } 
        
        //处理count和max的关系
        if (count > max) { //递归顺序问题,注意理解
            list.clear();
            list.add(root.val);
            max = count;
        } else if (count == max) {
            list.add(root.val);
        }
        
        findMode(root.right, list);
    }
}



    //public int[] findMode(TreeNode root) {
    //    // 超级暴力法
    //    // 获取map
    //    Map<Integer, Integer> map = new HashMap<>();
    //    findMode(root, map);
    //
    //    //处理map
    //    //出现的最多次数
    //    int maxCount = 0;
    //    //出现的最多次数的元素的个数
    //    int count = 0;
    //    for (Map.Entry<Integer, Integer> data : map.entrySet()) {
    //        //获取maxCount
    //        //16,3
    //        maxCount = Math.max(data.getValue(), maxCount);
    //    }
    //
    //    for (Map.Entry<Integer, Integer> data : map.entrySet()) {
    //        //获取count 出现的最多次数的元素的个数
    //        if (maxCount == data.getValue()) {
    //            count++;
    //        }
    //    }
    //
    //    //count确定,加入
    //    int[] res = new int[count];
    //    int index = 0;
    //    for (Map.Entry<Integer, Integer> data : map.entrySet()) {
    //        if (maxCount == data.getValue()) {
    //            res[index++] = data.getKey();
    //        }
    //    }
    //    return res;
    //}
    //
    //public void findMode(TreeNode root, Map<Integer, Integer> map) {
    //    //中序遍历
    //    if (root == null) {
    //        return;
    //    }
    //
    //    findMode(root.left, map);
    //    //处理
    //    addMapKeys(map, root.val);
    //    findMode(root.right, map);
    //}
    //
    //public void addMapKeys(Map<Integer, Integer> map, int key) {
    //    if (map.get(key) == null) {
    //        map.put(key, 1);
    //    } else {
    //        map.put(key, map.get(key) + 1);
    //    }
    //}



